Distributed cryptography deals with cryptographic services which are distributed amongst parties so that a plurality of the parties have to take action to perform an act. For example, a cryptographic function may be re-represented as distributed pieces. When given an input, the parties holding the pieces have to come up with a quorum of themselves, and each member of the quorum activates its piece over the input, resulting in a partial result for each member of the quorum. The partial results are combined into a final result that correctly represents a cryptographic function such as decryption, signature, or any other function. More particularly, the function may be based, for example, on discrete logarithm over a prime field or other domain or functions based on hardness of factoring.
A shared cryptographic function provides a service which has built-in distributed trust. In distributed trust services using shared cryptographic functions, the service operation is typically presented as a single coherent element which is managed centrally to achieve a uniquely identified sensitive function. The service has decentralized control for security against insiders and for geographic and/or organizational trust distribution. Shared cryptographic functions support cryptographic services such as certification authority and key escrow. Requirements of state-of-the-art technology impose stronger security and operational constraints than those present in existing systems. These constraints have forced integration of various technological components, thus introducing more complicated workflow relationships. These workflow relationships tend to be more complicated than input-output relationships and may require more than just careful access-control mechanisms.
In high-end secure systems which are not isolated, one cannot rely solely on software modules, operating systems, and physical security. Secure hardware tokens are often included in high-end secure systems to enhance security protection. Alternatively, cryptographic modules, e.g., co-processors, may be added as well as other cryptographic facilities, e.g., hardware or software. Hardware tokens are hosted under the software of the general purpose computing units. Thus, hardware units do not communicate with each other directly. The hardware tokens are the “most protected” system components, and thus the most trusted elements of high-end secure systems. To assure “end-to-end” security at the highest level, the hardware tokens should provide security themselves. Such explicit security seems to require an explicit “hand-shake” among the components, i.e., the hardware tokens. Such explicit “hand-shake,” however, overburdens the workflow by adding interactions, reduces performance, and adds to the required functionality by requiring mutual multi-party authentication of the limited computing environment at the hardware tokens.
The following references provide additional background of the invention and are incorporated herein by reference.    [A] R. J. Anderson, Why Cryptosystems Fail, Proceedings of the First Annual ACM Conference on Computer and Communications Security, CCS '93.    [B] R. Blakley, Safeguarding Cryptographic Keys, FIPS Con. Proc (v. 48), 1979, pp. 313–317.    [BF97] D. Boneh and M. Franklin, Efficient Generation of Shared RSA Keys, Crypto 97 proceedings.    [BDL] D. Boneh, R. DeMilo and R. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, Eurocrypt 97.    [B88] C. Boyd, Digital Multisignatures, IMA Conference on Cryptography and Coding, Claredon Press, 241–246, (Eds. H. Baker and F. Piper), 1989.    [BGS] J. Bull, L. Gong and K. Sollins, Towards Security in an Open Systems Federation, Esorics 92.    [DDFY] A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung, How to Share a Function Securely, ACM STOC '94, pp. 522–533.    [DF89] Y. Desmedt and Y. Frankel, Threshold cryptosystems, Advances in Cryptology-Crypto '97, pp. 307–315. Springer-Verlag.    [DF91] Y. Desmedt and Y. Frankel, Shared Generation of Authenticators and Signatures, Advances in Cryptology-Crypto '91, pp. 457–469. Springer-Verlag.    [DH] W. Diffie and M. Hellman, New Directions in Cryptography, IEEE Trans. on Information Theory 22(6), 1976, pp. 644–654.    [FIPS140] FIPS 140–1, Security requirements for cryptographic modules, National Institute of Standards and Technology, Jan. 1, 1994. (See also http://csrc.nist.gov/fips/)    [F89] Y. Frankel, A practical protocol for large group oriented networks, In J. J. Quisquater and J. Vandewalle, editor, Advances in Cryptology, Proc. of Eurocrypt '89, (Lecture Notes in Computer Science 773), Springer-Verlag, pp. 56–61.    [FGMY] Y. Frankel, P. Gemmel, P. Mackenzie and M. Yung. Proactive RSA, crypto 97.    [FGMY2] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung. Optimal Resilient Proactive Public-Key Systems, FOCS 97.    [FGY] Y. Frankel, P. Gemmel and M. Yung, Witness Based Cryptographic Program Checking and Robust Function Sharing. STOC96, pp.499–508.    [FMY] Y. Frankel, P. MacKenzie and M. Yung. Robust Distributed Efficient RSA-key Generation, manuscript.    [GJKR] R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Robust Threshold RSA, Crypto96, pp. 157–172.    [GGM] O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, J. Comm. Sci. 28 (1984), pp. 270–299.    [HJJKY] A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, M. Yung, Proactive Public-Key and Signature Schemes Proceedings of the Fourth Annual ACM Conference on Computer and Communications Security, CCS '97.    [JA] M. Joseph, and A. Avizienis, A Fault-Tolerance Approach to Computer Viruses, IEEE Sym. on Security and Privacy, 1988, pp. 52–58.    [K] R. Kocker, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSA and Other Systems, Crypto96.    [M] S. M. Matyas, Key processing with control vectors, Journal of Cryptology, 3(2), pp. 113–136, 1991.    [MT93] R. Molva and E. Tsudik, Authentication Methods with Impersonal Token Cards, IEEE Sym. on Security and Privacy, 1993, pp.56–65.    [OY] R. Ostrovsky and M. Yung, How to withstand mobile virus attacks, Proc. of the 10th ACM Symposium on the Principles of Distributed Computing, 1991, pp.51–61.    [RFLW] M. Reiter, M. K. Franklin, J. B. Lacy and R. N. Wright, The Ω Key Management Service Proceedings of the Third Annual ACM Conference on Computer and Communications Security, CCS '97.    [RSA] R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signature and Public Key Cryptosystems, Comm. of ACM, 21 (1978), pp. 120–126.    [Sh] A Shamir, How to share a secret, Comm. of ACM, 22 (1979), pp. 612–613.    [R] T. Rabin, A simplified approach to Threshold and Proactive RSA, Proceedings of Crypto 98, Spriner-Verlag, 1998, pp. 89–104.    [Y94] B. Yee, Using Secure Coprocessors, Ph.D. thesis, Carnegie Mellon University, Computer Science Tech. Report CMU-CS-94-149, May 1994.